#include "ufset.hpp"
#define SIZE 13

int UFSets[SIZE]; //  集合元素数组

// 初始化并查集
void Initial(int S[]) {
  for (int i = 0; i < SIZE; i++) {
    S[i] = -1;
  }
}

// Find “查”操作，找x所属集合
int Find(int S[], int x) {
  int root = x;
  while (S[root] >= 0) {
    x = S[root];
  }
  // 优化：压缩路径
  while (x != root) {
    int t = S[x];
    S[x] = root;
    x = t;
  }
  return root;
}

// Union “并”操作，小树合并到大树
void Union(int S[], int Root1, int Root2) {
  if (Root1 == Root2)
    return;
  if (S[Root2] > S[Root1]) {
    S[Root1] += S[Root2];
    S[Root2] = Root1;
  } else {
    S[Root2] = Root1;
    S[Root1] = Root2;
  }
}
